/** 
 * @file 1.数组和.cpp
 * @author 18-工程视觉-黄星照
 * @brief 阅读下列代码，回答代码最终输出，以及run1、run2时间复杂度各是什么
 * @date 2020-09-21
 */

/**
 * 
 * 1 4 9 16 25
 * run1: O(n^2)
 * run2: O(n)
 * 
 */

#include <iostream>
#include <vector>
class Solution
{
public:
    static ::std::vector<int> run1(::std::vector<int> nums)
    {
        ::std::vector<int> ret(nums.size());
        for (auto i = nums.begin(); i != nums.end(); ++i)
        {
            for (auto j = ret.begin(); j != ret.end(); ++j)
            {
                if (::std::distance(ret.begin(), j) >= ::std::distance(nums.begin(), i))
                    *j += *i;
            }
        }
        return ret;
    }
    static ::std::vector<int> run2(::std::vector<int> nums)
    {
        for (auto i = nums.begin() + 1; i != nums.end(); ++i)
        {
            *i = *i + *(i - 1);
        }
        return nums;
    }
};

int main(int argc, char **argv)
{
    ::std::vector<int> nums{1, 3, 5, 7, 9};
    auto ret = Solution::run1(nums);
    for (auto i : ret)
    {
        ::std::cout << i << ' ';
    }
}